#pragma once

#include "ConvexHullPoint.h"
#include <ClanLib/core.h>
#include <vector>
#include <cassert>

/*
 * data structure for saving convex hulls
 */
struct ConvexHull
{
	/*
	 * constructor that uses brute force algorithm to construct a convex hull with 2-3 points
	 * the points to be used are specified by points, startindex and endindex (both inclusive)
	 * don't use it, if more than 3 points are contained
	 */
	inline ConvexHull(const std::vector<clan::Vec2d>& points, int startIndex, int endIndex);
	/*
	 * alternative constructor helpfull for merging convex hulls, taking leftmost and rightmost point of an existing hull
	 * the ConvexHullPoints must be linked up correctly, this is not being taken care of in this constructor
	 */
	inline ConvexHull(ConvexHullPoint* leftmost, ConvexHullPoint* rightMost);
	/*
	* leftmost point of convex hull
	*/
	ConvexHullPoint* leftMostPoint;
	/*
	* rightmost point of convex hull
	*/
	ConvexHullPoint* rightMostPoint;
	/*
	* returns true, if this struct's constructor can be used to construct a convex hull from points with given indices 
	*/
	static inline bool IsBruteForceComputable(int startIndex, int endIndex);
	/*
	* returns the lines that represent the hull when drawn
	*/
	inline std::vector<clan::Line2d> GetLines( void );
	/*
	* true, if all points in the hull are below ore part of the given line
	*/
	inline bool IsFullyBelowLine(const ConvexHullLine& line) const;
	/*
	* handling similar to isBelowLine, just that all points of hull have to be below or part of given line
	*/
	inline bool IsFullyAboveLine(const ConvexHullLine& line) const;

	inline ConvexHull MergeRight( const ConvexHull& convexHullRight ) const;


};

inline bool ConvexHull::IsBruteForceComputable(int startIndex, int endIndex)
{
	return endIndex - startIndex + 1 <= 3;//true, if length of segment is three elements or lower
}

inline ConvexHull::ConvexHull( const std::vector<clan::Vec2d>& points, int startIndex, int endIndex )
	: leftMostPoint(new ConvexHullPoint(points[startIndex])),
	rightMostPoint(new ConvexHullPoint(points[endIndex]))
{
	switch (endIndex - startIndex + 1)
	{
	case 2:
		leftMostPoint->nextPointClockwise = leftMostPoint->nextPointCounterClockwise = rightMostPoint;
		rightMostPoint->nextPointClockwise = rightMostPoint->nextPointCounterClockwise = leftMostPoint;
		break;
	case 3:
		{
			auto middlePoint = new ConvexHullPoint(points[startIndex + 1]);
			if(middlePoint->IsBelowLine(leftMostPoint, rightMostPoint))//true, if middlepoint is above vector from leftmost to rightmost point
			{//left to right is clockwise
				leftMostPoint->nextPointClockwise = rightMostPoint;
				rightMostPoint->nextPointClockwise = middlePoint;
				middlePoint->nextPointClockwise = leftMostPoint;

				leftMostPoint->nextPointCounterClockwise = middlePoint;
				middlePoint->nextPointCounterClockwise = rightMostPoint;
				rightMostPoint->nextPointCounterClockwise = leftMostPoint;
			}
			else
			{//left to right is counterclockwise
				leftMostPoint->nextPointCounterClockwise = rightMostPoint;
				rightMostPoint->nextPointCounterClockwise = middlePoint;
				middlePoint->nextPointCounterClockwise = leftMostPoint;

				leftMostPoint->nextPointClockwise = middlePoint;
				middlePoint->nextPointClockwise = rightMostPoint;
				rightMostPoint->nextPointClockwise = leftMostPoint;
			}
		}
		break;
	default:
		assert(false);
	}
}

ConvexHull::ConvexHull( ConvexHullPoint* leftmost,  ConvexHullPoint* rightMost )
	: leftMostPoint(leftmost),
	rightMostPoint(rightMost)
{
}

std::vector<clan::Line2d> ConvexHull::GetLines( void )
{
	std::vector<clan::Line2d> lines;
	const ConvexHullPoint* intial = leftMostPoint;
	const ConvexHullPoint* actual = leftMostPoint;
	do
	{
		const ConvexHullPoint* next = actual->nextPointClockwise;
		lines.push_back(clan::Line2d(actual->location, next->location));
		actual = next;
	} while (actual != intial);
	return lines;
}

bool ConvexHull::IsFullyBelowLine( const ConvexHullLine& line ) const
{
	const ConvexHullPoint* intial = leftMostPoint;
	const ConvexHullPoint* actual = leftMostPoint;
	do
	{
		if(actual != line.left && actual != line.right)
		{
			if(!actual->IsBelowLine(line))
			{
				return false;
			}
		}
		actual = actual->nextPointClockwise;
	} while (actual != intial);
	return true;
}

bool ConvexHull::IsFullyAboveLine( const ConvexHullLine& line ) const
{
	const ConvexHullPoint* intial = leftMostPoint;
	const ConvexHullPoint* actual = leftMostPoint;
	do
	{
		if(actual != line.left && actual != line.right)
		{
			if(actual->IsBelowLine(line))
			{
				return false;
			}
		}
		actual = actual->nextPointClockwise;
	} while (actual != intial);
	return true;
}

inline ConvexHull ConvexHull::MergeRight( const ConvexHull& right ) const
{
	ConvexHullLine tangentUpper(rightMostPoint, right.leftMostPoint);
	while(!tangentUpper.left->nextPointCounterClockwise->IsBelowLine(tangentUpper)
		|| !tangentUpper.right->nextPointClockwise->IsBelowLine(tangentUpper))
	{
		while (!tangentUpper.left->nextPointCounterClockwise->IsBelowLine(tangentUpper))
		{
			tangentUpper.left = tangentUpper.left->nextPointCounterClockwise;
		}
		while (!tangentUpper.right->nextPointClockwise->IsBelowLine(tangentUpper))
		{
			tangentUpper.right = tangentUpper.right->nextPointClockwise;
		}
	}
	ConvexHullLine tangentLower(rightMostPoint, right.leftMostPoint);
	while (tangentLower.left->nextPointClockwise->IsBelowLine(tangentLower)
		|| tangentLower.right->nextPointCounterClockwise->IsBelowLine(tangentLower))
	{
		while (tangentLower.left->nextPointClockwise->IsBelowLine(tangentLower))
		{
			tangentLower.left = tangentLower.left->nextPointClockwise;
		}
		while (tangentLower.right->nextPointCounterClockwise->IsBelowLine(tangentLower))
		{
			tangentLower.right = tangentLower.right->nextPointCounterClockwise;
		}
	}
	tangentUpper.left->DeleteClockWiseUntil(tangentLower.left);
	tangentLower.right->DeleteClockWiseUntil(tangentUpper.right);
	tangentUpper.left->nextPointClockwise = tangentUpper.right;
	tangentUpper.right->nextPointCounterClockwise = tangentUpper.left;
	tangentLower.left->nextPointCounterClockwise = tangentLower.right;
	tangentLower.right->nextPointClockwise = tangentLower.left;
	return ConvexHull(leftMostPoint, right.rightMostPoint);
}